Modem data processors incorporate features related to a performance strategy known as address translation. Data processors that incorporate address translation schemes manipulate one set of addresses internally and another set externally for each location in memory space. Addresses manipulated internal to the data processor are often referred to as "effective" or "virtual" addresses. Addresses manipulated external to the data processor are often referred to as "real" or "physical" addresses.
Data processors that incorporate address translation schemes have several advantages relative to data processors without address translating abilities. First, address translation schemes permit a data processor to access "virtual memory" beyond its real addressing boundaries. Typically, virtual memory is memory "space" on a hard disk drive. Second, address translation schemes allow multiple application programs to simultaneously reside in a data processing system's memory without the danger of one application corrupting the data of another application. Third, address translation schemes permit multiple applications to access common data in memory even though each application will generate a different virtual address for the common data.
Data processors maintain tables that contain mappings to translate effective addresses to real addresses whenever the data processor accesses an external device. These tables may be located in main memory, in specialized internal memory arrays within the data processor or in both. Oftentimes, a data processor will maintain a subset of all possible address translation mappings in a high-speed internal cache, "a translation lookaside buffer or TLB." These data processors maintain all possible address translation mappings externally, in main memory. The data processor accesses the slow main memory tables for a translation mapping when the TLB is not able to translate a particular effective address. The data processor then stores the translation mapping in the TLB for future reuse. As a consequence, the data processor must have some strategy for selecting a less useful translation mapping, discarding it, and storing the new translation mapping in the same location once the TLB is fully populated. However, any fixed replacement algorithm is a compromise between all possible operating scenarios.